The cost of managing storage systems has gone up drastically in recent years. These cost increases are due to the increasing complexity of such systems—required to cope with an increase in the rate of data growth and demands on performance, reliability and availability. As a result, there is a growing trend towards outsourcing of storage to managed storage service providers (SSPs). The providers host the customer's data on large-scale consolidated storage systems that are based on a networked architecture typically consisting of servers, switches, disk array controllers, caches, and disks, and often referred to as storage area networks (SANs). FIG. 1 shows a typical SAN 50 A comprising storage servers 10, storage devices 30 and interconnecting switches 20.
Traditionally, attempts to optimize enterprise storage have focussed on reducing the cost of storage solutions. However in a SSP scenario, “best effort” service from low cost solutions may be unacceptable—elaborate Service Level Agreements (SLAs) specifying quality of service (QoS) guarantees and revenue parameters may be agreed between the provider and the customers. The SSP's resources are shared shared among applications and/or customers with different QoS requirements and associated rewards and penalties. The resources must be allocated and work scheduled in such a way that all customers are satisfied. One aspect of this problem is the scheduling of execution of I/O requests that arrive at a magnetic hard disk in a provider's system.
Various scheduling algorithms have been proposed for scheduling disk read and write operations in non-SSP environments. Typically, these methods are non-predictive—looking only at requests that have already been received—and the generated schedules and allocation of resources do not take account of the relative importance of each request to the profits and revenues of a storage service provider.
Most of the previous work on disk scheduling has focussed on optimizing the time that the disk head spends in moving to the right position to service the requests and/or meeting the deadlines of real-time workloads. Among the most well-known are the ones that optimize the seek: SSTF (shortest seek-time first), SCAN, C-SCAN (circular SCAN); and ones that optimize both seek and rotation: STF (shortest time first), and its variants like GSTF (grouped shortest time first). The real-time scheduling algorithms were mostly developed for servicing multimedia workloads. They include EDF (earliest deadline first) and variants such as SCAN-EDF and SSEDV (shortest seek and earliest deadline by value) that optimize seek and rotational latency while still meeting the request deadlines. These algorithms do not take into account the priority or profits associated with a request while making scheduling decisions. Thus, they are fundamentally incapable of providing profit- or revenue-differentiated QoS or maximizing profits in a service provider setting.
More recently, some algorithms have been proposed that can support diverse QoS classes. Bruno et al. “Disk Scheduling with Quality of Service Guarantees”, Proceedings of International Conference on Multimedia Computing and Systems, 1999, proposed a proportional share scheduler, YFQ, that enables applications to reserve portions of disk bandwidth. YFQ can provide QoS guarantees at individual application level, but YFQ is unsuitable in a service provider setting because the scheduler does not support rewards that are independent of the disk usage shares.
A disk scheduling framework is described by Shenoi et al, in “Cello: A Disk Scheduling Framework for Next Generation Operating Systems”, Proceedings of ACM SIGMETRICS, 1998, pages 44-55. The Cello disk scheduling framework employs a two level scheduler with a top level proportional share scheduler assigning disk shares to low level schedulers that can use different scheduling techniques depending on the workload type. However, Cello does not provide for revenue or profit maximization for the same reasons as YFQ.
Such methods have provided advantages, but no scheduling techniques have been described which are satisfactory to optimize profits or revenues in a storage service environment.